package com.zs.letcode.illustration_of_algorithm;

/**
 * 剑指 Offer 04. 二维数组中的查找
 * 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 * <p>
 *
 * <p>
 * 示例:
 * <p>
 * 现有矩阵 matrix 如下：
 * <p>
 * [
 * [1,   4,  7, 11, 15],
 * [2,   5,  8, 12, 19],
 * [3,   6,  9, 16, 22],
 * [10, 13, 14, 17, 24],
 * [18, 21, 23, 26, 30]
 * ]
 * 给定 target=5，返回true。
 * <p>
 * 给定target=20，返回false。
 * <p>
 *
 * <p>
 * 限制：
 * <p>
 * 0 <= n <= 1000
 * <p>
 * 0 <= m <= 1000
 * <p>
 *
 * <p>
 * 注意：本题与主站 240 题相同：https://leetcode-cn.com/problems/search-a-2d-matrix-ii/
 * <p>
 * 相关标签
 * 数组
 * 二分查找
 * 分治
 * 矩阵
 * <p>
 * Python3
 * <p>
 * <p>
 * <p>
 * 作者：Krahets
 * 链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5v76yi/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author madison
 * @description
 * @date 2021/8/25 09:17
 */
public class Chapter50 {

    public static void main(String[] args) {

    }

    private class Solution {
        /**
         * 方法一：暴力法
         */
        public boolean findNumberIn2DArray(int[][] matrix, int target) {
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix[i].length; j++) {
                    if (matrix[i][j] == target) {
                        return true;
                    }
                }
            }
            return false;
        }

        /**
         * 方法二：二分法搜索
         */
        public boolean findNumberIn2DArray1(int[][] matrix, int target) {
            // an empty matrix obviously does not contain `target`
            if (matrix == null || matrix.length == 0) {
                return false;
            }

            // iterate over matrix diagonals
            int shorterDim = Math.min(matrix.length, matrix[0].length);
            for (int i = 0; i < shorterDim; i++) {
                boolean verticalFound = binarySearch(matrix, target, i, true);
                boolean horizontalFound = binarySearch(matrix, target, i, false);
                if (verticalFound || horizontalFound) {
                    return true;
                }
            }

            return false;
        }

        private boolean binarySearch(int[][] matrix, int target, int start, boolean vertical) {
            int lo = start;
            int hi = vertical ? matrix[0].length - 1 : matrix.length - 1;

            while (hi >= lo) {
                int mid = (lo + hi) / 2;
                if (vertical) { // searching a column
                    if (matrix[start][mid] < target) {
                        lo = mid + 1;
                    } else if (matrix[start][mid] > target) {
                        hi = mid - 1;
                    } else {
                        return true;
                    }
                } else { // searching a row
                    if (matrix[mid][start] < target) {
                        lo = mid + 1;
                    } else if (matrix[mid][start] > target) {
                        hi = mid - 1;
                    } else {
                        return true;
                    }
                }
            }

            return false;
        }

        /**
         * 方法三：搜索空间的缩减
         */
        private int[][] matrix;
        private int target;

        private boolean searchRec(int left, int up, int right, int down) {
            // this submatrix has no height or no width.
            if (left > right || up > down) {
                return false;
                // `target` is already larger than the largest element or smaller
                // than the smallest element in this submatrix.
            } else if (target < matrix[up][left] || target > matrix[down][right]) {
                return false;
            }

            int mid = left + (right - left) / 2;

            // Locate `row` such that matrix[row-1][mid] < target < matrix[row][mid]
            int row = up;
            while (row <= down && matrix[row][mid] <= target) {
                if (matrix[row][mid] == target) {
                    return true;
                }
                row++;
            }

            return searchRec(left, row, mid - 1, down) || searchRec(mid + 1, up, right, row - 1);
        }

        public boolean searchMatrix(int[][] mat, int targ) {
            // cache input values in object to avoid passing them unnecessarily
            // to `searchRec`
            matrix = mat;
            target = targ;

            // an empty matrix obviously does not contain `target`
            if (matrix == null || matrix.length == 0) {
                return false;
            }

            return searchRec(0, 0, matrix[0].length - 1, matrix.length - 1);
        }

        /**
         * 方法四：
         */
        public boolean findNumberIn2DArray2(int[][] matrix, int target) {
            int row = matrix.length - 1;
            int col = 0;
            while (row >= 0 && col < matrix[0].length) {
                if (matrix[row][col] > target) {
                    row--;
                } else if (matrix[row][col] < target) {
                    col++;
                } else {
                    return true;
                }
            }
            return false;
        }
    }
}
